import java.util.ArrayList;
import java.util.List;

import javax.swing.tree.TreeNode;

/*
 * @lc app=leetcode.cn id=501 lang=java
 *
 * [501] 二叉搜索树中的众数
 *
 * https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/description/
 *
 * algorithms
 * Easy (42.62%)
 * Likes:    68
 * Dislikes: 0
 * Total Accepted:    7K
 * Total Submissions: 16.3K
 * Testcase Example:  '[1,null,2,2]'
 *
 * 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
 *
 * 假定 BST 有如下定义：
 *
 *
 * 结点左子树中所含结点的值小于等于当前结点的值
 * 结点右子树中所含结点的值大于等于当前结点的值
 * 左子树和右子树都是二叉搜索树
 *
 *
 * 例如：
 * 给定 BST [1,null,2,2],
 *
 * ⁠  1
 * ⁠   \
 * ⁠    2
 * ⁠   /
 * ⁠  2
 *
 *
 * 返回[2].
 *
 * 提示：如果众数超过1个，不需考虑输出顺序
 *
 * 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
 *
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int curNum = -1;
    int maxCnt = 1;
    int curCnt = 0;
    List<Integer> list = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        mid(root);
        int[] res = new int[this.list.size()];
        for(int index=0; index < res.length; index++) {
            res[index] = this.list.get(index);
        }

        return res;
    }

    void mid(TreeNode root) {
        if(root == null) {
            return;
        }
        mid(root.left);
        if(this.curNum == -1) {
            this.curNum = root.val;
        }

        if(root.val == this.curNum) {
            this.curCnt++;
        } else {
            this.curCnt = 1;
            this.curNum = root.val;
        }

        if(this.curCnt > this.maxCnt) {
            this.maxCnt = this.curCnt;
            this.curNum = root.val;
            this.list = new ArrayList<>();
            this.list.add(root.val);
        } else if(this.curCnt == this.maxCnt) {
            this.list.add(root.val);
        }

        mid(root.right);
    }
}
// @lc code=end

